# -*- coding: utf-8 -*-

"""剑指 Offer II 052. 展平二叉搜索树
给你一棵二叉搜索树，请 按中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。

示例 1：
输入：root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

示例 2：
输入：root = [5,1,7]
输出：[1,null,5,null,7]

提示：
树中节点数的取值范围是 [1, 100]
0 <= Node.val <= 1000"""


# Definition for a binary tree node.
from typing import OrderedDict


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def increasingBST(self, root: TreeNode) -> TreeNode:
        left_order, right_order = None, None
        if root.left:
            left_order = self.increasingBST(root.left)
            tail = root.left
            while tail.right:
                tail = tail.right
        if root.right:
            right_order = self.increasingBST(root.right)

        if left_order:
            tail.right = root
            root.left = None
            root.right = right_order
            return left_order
        else:
            root.left = None
            root.right = right_order
            return root


def right_print(node):
    while True:
        try:
            print(node.val)
            node= node.right
        except AttributeError:
            break

if __name__ == "__main__":
    so = Solution()
    root = TreeNode(5, TreeNode(3, TreeNode(2, TreeNode(1)), TreeNode(4)), TreeNode(6, None, TreeNode(8, TreeNode(7), TreeNode(9))))
    order = so.increasingBST(root)
    right_print(order)
